import java.util.Scanner;

public class test {

    // 关系矩阵，存储集合中的盖住关系
    public static int[][] helpMatrix = new int[100][100];
    public static int maxElement = 0; // 用于存储集合中的最大元素

    // 求集合A上的整除关系R对应的盖住关系
    public static void coverRelation(int[] arr, int n) {
        // 对关系矩阵进行初始化
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                // 判断满足整除关系的同时保证去除自反性
                if (arr[i] % arr[j] == 0 && arr[i] != arr[j]) {
                    helpMatrix[arr[i]][arr[j]] = 1;
                }
            }
        }

        // 去除关系中的传递性及自反性 -> 得到盖住关系
        for (int i = 1; i < 100; i++) {
            for (int j = 1; j < 100; j++) {
                for (int k = 1; k < 100; k++) {
                    if (helpMatrix[i][j] == 1 && helpMatrix[j][k] == 1) {
                        helpMatrix[i][k] = 0;
                    }
                }
                helpMatrix[i][i] = 0;
            }
        }

        // 打印盖住关系
        for (int i = 0; i < 100; i++) {
            for (int j = 0; j < 100; j++) {
                if (helpMatrix[i][j] == 1) {
                    System.out.print("{" + j + "," + i + "}" + " ");
                }
            }
        }
        System.out.println();
    }

    // 判断偏序集是否为格
    public static boolean isLattice(int[] arr, int n) {
        // 检查每个元素对 (i, j) 是否有唯一的上界和下界
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (helpMatrix[arr[i]][arr[j]] == 1) {
                    int gcd = gcd(arr[i], arr[j]);
                    int lcm = lcm(arr[i], arr[j]);

                    // 检查 gcd 和 lcm 是否在集合中
                    boolean gcdExists = false, lcmExists = false;
                    for (int k = 0; k < n; k++) {
                        if (arr[k] == gcd) gcdExists = true;
                        if (arr[k] == lcm) lcmExists = true;
                    }

                    if (!gcdExists || !lcmExists) {
                        return false;
                    }
                }
            }
        }
        return true;
    }

    // 判断是否为有补格
    public static boolean isComplementedLattice(int[] arr, int n) {
        if (!isLattice(arr, n)) return false;

        // 找到集合中的最小元（通常是1）和最大元（集合中的最大值）
        int minElement = Integer.MAX_VALUE;
        for (int num : arr) {
            if (num == 1) {
                minElement = 1; // 如果集合中有1，则最小元为1
                break;
            }
            if (num < minElement) {
                minElement = num;
            }
        }
        maxElement = 0;
        for (int num : arr) {
            if (num > maxElement) {
                maxElement = num;
            }
        }

        // 检查每个元素是否都有补元
        for (int a : arr) {
            boolean foundComplement = false;
            for (int b : arr) {
                if (b != a && gcd(a, b) == minElement && lcm(a, b) == maxElement) {
                    foundComplement = true;
                    break;
                }
            }
            if (!foundComplement) {
                return false;
            }
        }
        return true;
    }

    // 辅助函数：求两个元素的最大公因数（GCD）
    public static int gcd(int x, int y) {
        while (y != 0) {
            int temp = y;
            y = x % y;
            x = temp;
        }
        return x;
    }

    // 辅助函数：求两个元素的最小公倍数（LCM）
    public static int lcm(int x, int y) {
        return (x * y) / gcd(x, y);
    }

    public static void main(String[] args) {
        // 输入集合A中元素的个数n
        System.out.println("Please enter the number of elements in the set:");
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();

        // 创建一个长为n的一维数组，对A中的元素进行存储
        System.out.println("Please input the elements of the set:");
        int[] arr = new int[n];
        for (int i = 0; i < n; i++) {
            arr[i] = in.nextInt();
        }

        //打印盖住关系
        System.out.println("The covered relationship is");
        coverRelation(arr, n);

        // 判断是否为有补格
        boolean isComplemented = isComplementedLattice(arr, n);
        if(isComplemented)
            System.out.println("The poset is a complemented lattice.");
        else
            System.out.println("The poset is not a complemented lattice.");
    }
}
